The present invention relates to a control system for buffer storage equipment to be shared by a plurality of processing units.
A method for configuring a system which has a large capacity buffer storage shared by a plurality of processing units and provided between a buffer storage unit within each processing unit and a main storage unit, aims at improvement in the access time to the main storage unit by the shared buffer storage. This technique is suitable for the case where there is a large difference between the access time to the main storage unit and the processing time of the processing unit. The M-68xH processing system manufactured by Hitachi, Ltd. is one of the examples of a computer system having such a configuration. The configuration of this processing system is described in the "M-68x Processor Group Functional Manual" 6080-2-002, Hitachi, Ltd. Each of the processing units has a buffer storage unit (hereinafter to be referred to as a BS) of the store-through type control for each processing unit and every pair of processing units have one shared work buffer storage (hereinafter to be referred to as a WS) of the store-in type.
In the above system, when data in the main storage unit is necessary for executing an instruction in a processing unit, the BS is accessed to determine whether the necessary data exists in the BS. If the necessary data is not buffered in the BS, a transfer request for this data is generated and sent to the WS by the processing unit. The data transfer from the WS to the BS is performed in fixed amount of data called a block. The WS detects whether a block corresponding to this request is buffered within the WS. If the block exists in the WS, the data is read out from the WS and is transferred to the BS of the requesting processing unit.
There is another technique for guaranteeing an order of main storage references in a multiprocessor configuration. In such a system having a plurality of processing units, the instruction execution time for each processing unit varies depending on the state of the buffer storage unit within the processing unit or the occurrence of an interruption. Therefore, it is generally difficult to synchronize executions of instructions among the plurality of processing units. As a result, it becomes necessary to guarantee the order of references to the main storage by each processing unit in order to secure consistency between the processing units in accessing of the main storage unit. For example, in the "370/XA Principles of Operation", SA22-7085, 5-24.about.5-30, IBM Co., Ltd., the following conditions are defined so as to meet the above requirement. That is, "A sequence of reference or updating a main storage equipment by a processing unit does not necessarily coincide with an instruction execution order in the processing unit. However, it should not be observed by the other processing unit connected to the same storage that the processing unit processes the accesses of the main storage with a different order of the instruction sequence". The term `observation` in the above description means that another processor can read data in the main storage that couldn't exist in the main storage if that processing unit would process the accesses to the main storage according to the same order of the instruction sequence.
In the guarantee of the processing order as indicated in the above document, it is not necessary to process the requests from the processing units in order in the main storage unit or the WS so long as there is no inconsistency in the results of the instruction executions. However, referring and writing operations by the other processing units are separately processed. Therefore, in the case where a processing method has been employed in which the processing is carried out with an out-of order sequence, some additional restriction of processing is necessary so that it can be guaranteed that irrational data not corresponding to a request equipment is not read out from the main storage, in the case where an updating order has been kept for the other processing units. However, it is difficult to realize such processing as described above if considering the case of a failure, and a method has been conventionally employed in which processing is carried out while keeping the updating order. For example, in order to guarantee the order of the above description, when a preceding processing is being kept in a wait table for some reason generated in the buffer storage, it is so controlled that the request of the following processing of data in the buffer storage equipment wouldn't be carried out before the preceding processing. JP-A-61-45355 realizes this method as an example of the prior art. According to this prior art technique, a request selection system is shown in which a succeeding request is selected after a signal has been received which indicates that processing for a preceding request has been completed.
As another type of prior art technique, a technique for pipeline processing using a buffer storage is known. A response time is important for a buffer storage unit within the processing unit, whereas providing a high throughput of processing as well as the response time is important for design of the buffer storage. And, some implementations of buffer storage, applied pipeline processing method which are commonly used in constructing arithmetic processing unit, are known.
An example of the pipeline processing will be explained below. In the buffer storage shared by the processing units, the following three types of processing are sequentially carried out to process a request for reference to or updating of data in the buffer storage unit by the processing units.
(1) Arbitrate requests from the processing units and select one from among them. (This processing will be called a P stage hereinafter.) PA1 (2) Refer to the buffer storage to test whether data meeting the request selected in the P stage is stored in the buffer storage. (This processing will be called a J stage hereinafter.) PA1 (3) Pass the request that requires the data that is buffered in the buffer storage, the existence of which in the buffer storage has been tested in the J stage. PA1 (4) The buffer storage equipment reads out the data from the buffer storage equipment or updates the data. (This processing will be called a W stage hereinafter.)
Assuming that the processing corresponding to each of the above stages can be executed in one cycle, a total of four cycles are necessary to process one request. In the pipeline processing method using a buffer storage unit, as described above, the time required for processing is not reduced by overlappingly executing the respective stages, but a new request is processed in each cycle, so that the total throughput is equivalently improved.
As another conventional method of improving throughput, a structure is known in which the number of requests that can be accepted at one time is increased by improving the parallel processing capability. This method can be used together with the pipeline method. When this method is applied to the above processing example, it is possible to select a plurality of requests at the P stage and to simultaneously process the plurality of requests during one cycle at each of the subsequent stages including the J stage. For example, in the buffer storage which employs the above-described pipeline processing method, when a plurality of cycles are required to read data from a memory because of the slow R/W operation of the memory, a plurality of memory sections are provided and the plurality of memory sections are simultaneously operated to attain the necessary performance. An example of a data flow in the pipeline processing for executing the above control is shown in FIG. 4. FIG. 4 shows a case where two cycles are required for the W stage and two processings can be executed in parallel at the W stage, which are indicated by W.sub.0 and W.sub.1 in the drawing.
In the buffer storage employing pipeline processing, which is explained in the above prior art example, the above-described processing order control in the buffer storage is achieved by keeping at each stage the order of requests selected at the P stage. An example of this control is shown in FIG. 5. For example, subsequent to a request 1 from a processing unit A for starting a buffer storage section W.sub.0, assume that a request 2 from the processing unit A for simultaneously starting two buffer storage sections (W.sub.0 and W.sub.1) is generated at a cycle that the processing of the preceding request 1 has been completed. For the idle buffer storage section W.sub.1, a request 3, which uses only the buffer storage section W.sub.1, from the other processing unit B is processed with a priority so that the processing order can be guaranteed. Therefore, the request 2 from the processing unit A for using the two buffer storage sections as shown in FIG. 5, cannot be submitted until the preceding request 1 has been completed. On the other hand, the request 3 from the processing unit B, which has arrived later than the request 2, can be processed earlier than the preceding request 2 which uses the two buffer storage sections. When the request 3 is processed earlier, it is possible to reduce the idle time of the buffer storage, so that the buffer storage can be effectively used.
However, the system in which a request is issued to the buffer storage while predicting a busy state of the buffer storage, has a problem that a request from the processing unit for reading block data cannot be processed quickly. In general, such a read request from the processing unit to the shared buffer storage transfers the requested data as a fixed amount of data (hereinafter to be referred to as a block) of to the buffer storage unit (hereinafter to be referred to as a BS) within the processing unit. However, in this case, the data for processing the processing in the execution unit within the processing unit (hereinafter to be referred to as target data) is a part of the block data. In order to satisfy the data request from the execution unit to the BS, it is sufficient if it is possible to send only target data to the execution unit. The remaining data of the block is for expecting the effect of a prefetch. Therefore, sending the block data, the sending time of the target data becomes critical to the performance. Sending of the other portion of the block data may be slightly late. And, the block data is relatively larger than the store data. Therefore, when reading the block data, it is necessary to provide control such that a plurality of storage units within the buffer storage unit are activated simultaneously so that the time of reading the block data can be reduced. But as is described before, in the control method for predicting a busy state of the buffer storage unit, when a block transfer for a preceding request is to be started, the next request cannot be submitted until all of the buffer control sections to be used for the block transfer become free. Accordingly, there is less opportunity of submitting a request for using a plurality of buffer storage units at once, such as a request for a block transfer, than the opportunity of submitting a request for using only one buffer storage unit. As a result, it takes a long time before the request for processing in the buffer storage unit can be submitted, leading to decline in the performance of the system due to the increase in the response time.